/*
	Dupmerge2, idea based on dupmerge by Phil Karn rewritten in C++

 Copyright 2011 Ludovic Seegmuller. May be used under the terms of the GNU Public License.

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/


/*
#include <stdio.h>#include <string.h>             // strndup,
#include <iso646.h>             // for and, bitand, or, bitor ...
#include <stdbool.h>            // _Bool
#include <signal.h>             // signals
#include <limits.h>             // UCHAR_MAX
#include <sys/mman.h>           // mlockall
#include <sys/wait.h>           // vfork
#include <time.h>               // localtime
*/

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <ftw.h>

#include <stdlib.h>

#include <iostream>
#include <errno.h>
#include <fstream>
#include <string.h>

typedef long fileindex_t;
typedef long progressindex_t;
typedef long bufferindex_t;


#define bufferlength 16777216 // 16MB

using namespace std;

class dupentry
{
public:
	char * name;
	dupentry * previous; // used a link to the previous entry

	dev_t st_dev;
	ino_t st_ino;
	off_t st_size;
	blkcnt_t st_blocks;
;
	bool processed;
};

class dupmerge2
{
public:
	dupmerge2();
	~dupmerge2();

	void			readarguments(const int argc, const char *const argv[]);
	void			process();

protected:
	void			step1();
	void			step2();
	void			step3();
	void			step4();

	void 			sort_array(dupentry** source, dupentry**temp, int size, progressindex_t progr);
	bool 			compare_entries(dupentry* e1, dupentry* e2);
	bool 			compare_files(dupentry* e1, dupentry* e2);

	static int 		add_file_routine(const char *fpath, const struct stat *sb, int typeflag, struct FTW *ftwbuf);
	int 			add_file(const char *fpath, const struct stat *sb, int typeflag);

public:
	static dupmerge2* sCurrent;
protected:
	static const char* sVersion;
	const char*		searchpath;
	progressindex_t	progress, progressmax;
	time_t			timestart, timeupdate;
	
	dupentry**		array;
	long			arraysize;
	dupentry*		preallocarray; // used to preallocate entries by group of 1024
	long			preallocindex, preallocmax;
	long			saved;
	
	dupentry *		previous;
	dupentry *		current;

	char*			buffer1;
	char*			buffer2;

	bool 			fverbose, fzenity, ftest, fversion;
};

const char* dupmerge2 :: sVersion = "0.1";
dupmerge2* dupmerge2 :: sCurrent = NULL;

// TODO translate messages
// TODO clean-up verbose & co
// TODO homogeneous error messages

int main(const int argc, const char *const argv[])
{	
	dupmerge2* dm = new dupmerge2();
	dm->readarguments(argc, argv);
	dm->process();
}

dupmerge2 :: dupmerge2()
{
	sCurrent = this;
	previous = 0; current = 0;
	preallocindex = 1024;
	preallocmax = 1024;
	arraysize = 0;
	saved = 0;

	fverbose = false;
	fzenity = false;
	ftest = false;
	fversion = false;
}

dupmerge2 :: ~dupmerge2()
{
}

void dupmerge2 :: readarguments(const int argc, const char *const argv[])
{	
	int opt;
	// read command line options
	while ((opt = getopt(argc, (char *const *) argv, "tvVzh")) != EOF) {
		switch (opt) {
			case 't':
				ftest = true;
				break;
			case 'v':
				fverbose = true;
				break;
			case 'V':
				fversion = true;
				break;
			case 'z':
				fzenity = true;
				break;
			case 'h':
				cout << "dupmerge2 scans files on disk, find identical files and hardlink them so that duplicate don't use" << endl;
				cout << "unnecessary memory... " << endl;
				cout << " -t\tdoes not apply changes" << endl;
				cout << " -v\tverbose mode" << endl;
				cout << " -V\tshow version and exit" << endl;
				cout << " -z\toutput designed for zenity --progress" << endl;
				cout << " -h\tshow this help" << endl;
				exit(0);
			default:
				break;
		}
	}
	if (argc > 1) {
		searchpath = argv[argc-1];
	} else {
		cerr << "dupmerge2: Need to provide at least a path to search in" << endl;
		exit(-1);
	}
}

void dupmerge2 :: process()
{
	if (fversion) {
		cout << "Duplicates merger dupmerge " << dupmerge2 :: sVersion << endl;
		cout << "remade in C++ by Ludovic Seegmuller" << endl;
		cout << "based on dupmerge by Phil Karn and Rolf Freitag" << endl;
	}

	//searchpath = "./TEST2/";
	//searchpath = "/media/backup7/backup";

	step1();
	step2();
	step3();
	step4();
}


// creates a list of the files in the provided directory
void dupmerge2 :: step1()
{
	if (fzenity) {
		cout << "#[1/4] Lecture des fichiers" << endl;
		cout << 0 << endl;
	}
	progress = 0; progressmax = 10000000;
	timestart = time(NULL); timeupdate = 0;


	long error;
	error = nftw(searchpath, dupmerge2 :: add_file_routine, 1024, FTW_PHYS | FTW_MOUNT);
	if (error) {
		cerr << "Error with ftw : " << error << endl;
		perror("nftw");
		exit(-1);
	}
	
	cout << progress << " fichiers trouvés" << endl;
}

// Routine called by ftw (scan directory tree), checks if it's a regular file, not empty, with blocks
// and add it to a chained list
int dupmerge2 :: add_file_routine(const char *fpath, const struct stat *sb, int typeflag, struct FTW *) 
{
	return dupmerge2::sCurrent->add_file(fpath, sb, typeflag);
}

int dupmerge2 :: add_file(const char *fpath, const struct stat *sb, int typeflag) 
{
	//cout << (FTW_F == typeflag) << " " << (sb->st_size ) << " " << (sb->st_blocks )<< " " << fpath << endl;
	if ((FTW_F == typeflag) && (sb->st_size >0) && (sb->st_blocks >0)) {

		// do we need to (re-)preallocate entries ?
		if (preallocindex == preallocmax) {
			preallocarray = new dupentry[preallocmax];
			preallocindex = 0;
		}
		previous = current;
		current = &preallocarray[preallocindex++];
		arraysize++;

		// create entries
		current->name = strdup(fpath);
		current->st_dev = sb->st_dev;
		current->st_ino = sb->st_ino;
		current->st_size = sb->st_size;
		current->st_blocks = sb->st_blocks;
		current->previous = previous;
		current->processed = false;

		if (fzenity) progress++;
		if (fzenity) if (!(progress % 8096)) {
			long elapsed, speed, remaining;
			elapsed = (time(NULL)-timestart) + 1;
			speed = progress / elapsed;
			remaining = (progressmax - progress)/speed;
			cout << "#[1/4] Lecture des fichiers (" << progress << ", " << (speed / 1000) << " kfiles/sec, "
					<< (remaining/60) << ":" << (remaining%60) << " restants)" << endl;
			cout << progress*100 / progressmax << endl;
		}
	}
	return 0;
}


void dupmerge2 :: step2()
{
	if (fzenity) {
		cout << "#[2/4] Récupération des infos des fichiers" << endl;
		cout << 0 << endl;
	}
	progress = 0; progressmax = arraysize;
	timestart = time(NULL); timeupdate = 0;

	long i = 0;
	array = new dupentry*[arraysize];

	
	while (current != 0) {
		array[i++] = current;
		current = current->previous;

		if (fzenity) progress++;
		if (fzenity) if (!(progress % 32768)) {
			long elapsed, speed, remaining;
			elapsed = (time(NULL)-timestart)+1;
			speed = progress / elapsed+1;
			remaining = (progressmax - progress) / speed;
			cout << "#[2/4] Récupération des infos des fichiers (" << progress << "/" << progressmax << ", " << (speed / 1000) 
					<< " kfiles/sec, " << (remaining/60) << ":" << (remaining%60) << " restants)" << endl;
			cout << progress*100 / progressmax << endl;
		}
	}
}

void dupmerge2 :: step3()
{
	if (fzenity) {
		cout << "#[3/4] Tri de la liste" << endl;
		cout << 0 << endl;
	}

	progress = 0; progressmax = arraysize;
	timestart = time(NULL); timeupdate = 0;
	
	dupentry** temparray = new dupentry*[arraysize];
	sort_array(array, temparray, arraysize, 0);
	for (int i=0;i<arraysize;i++)
		cout << i << " " << array[i]->st_dev << " " << array[i]->st_size << " " << array[i]->st_ino << " " << array[i]->name << endl;

}

void dupmerge2 :: sort_array(dupentry** source, dupentry**temp, int size, progressindex_t progr)
{
	int i1, i2, j, k;
	dupentry **l1, **l2;
	if (size>1) {
		// cout << 100.0 * progr / (progrmax) << endl;
		// cout << "#[3/4] Tri de la liste (" << progr << "/" << progrmax << ")" << endl;
		// for (i=0; i<size; i++) cout << " start " << source[i]->name << endl;

		l1 = source;
		l2 = &source[size/2];
		i1=0; i2=0;
		sort_array(l1, temp, size/2, progr);
		sort_array(l2, temp, size-size/2, progr+size/2);

		i1 = 0; i2 = 0; j = 0;
		while ((i1 < size/2) || (i2 < size-size/2)) {
			if (i1 < size/2) {
				if (i2 < size - size/2) {
					if (compare_entries(l1[i1], l2[i2])) {
						temp[j++] = l1[i1++];
					} else {
						temp[j++] = l2[i2++];
					}
				} else {	
					temp[j++] = l1[i1++];
				}
			} else {
				if (i2 < size - size/2) {
					temp[j++] = l2[i2++];				
				} else {	
					cout << "Erreur: les deux listes sont terminées" << endl;
					break;
				}
			}
		}
		
		if (fzenity) if (time(NULL) != timeupdate) {
			cout << (progr+size)*100 / progressmax << endl;
			cout << "#[3/4] Tri de la liste (" << (progr+size) << "/" << progressmax << ")" << endl;
			timeupdate = time(NULL);
		}

		// cout << "Traité:" << temp[j-1]->name << endl;
		// copy back to source now that it's ordered
		// for (i=0; i<size; i++) cout << " outtemp " << temp[i]->name << endl;
		for (k=0; k<j; k++)
			source[k] = temp[k];
		// for (i=0; i<size; i++) cout << " out " << source[i]->name << endl;
		// cout << "fermeture " << size << endl;

	} else if (size < 1) {
		cout << "Erreur de taille!" << endl;
		exit(-1);
	}
}

bool dupmerge2 :: compare_entries(dupentry* e1, dupentry* e2)
{
	if (e1->st_dev < e2->st_dev)
		return true;
	if (e1->st_dev > e2->st_dev)
		return false;
	if (e1->st_size > e2->st_size)
		return true;
	if (e1->st_size < e2->st_size)
		return false;
	return (e1->st_ino < e2->st_ino);
}


void dupmerge2 :: step4()
{
	if (fzenity) {
		cout << "#[4/4] Recherche de doublons" << endl;
		cout << 0 << endl;
	}
	progress = 0; progressmax = arraysize;
	timestart = time(NULL); timeupdate = 0;

	long i=0, offset, offset2, error;
	
	buffer1 = new char[bufferlength];
	buffer2 = new char[bufferlength]; 

	cout << "progressmax" << progressmax << endl;

	while (i < arraysize) {
		if (array[i]->processed) {
			i++;
			continue;
		}
		if (fverbose) cout << "Starting with: " << array[i]->name << endl;
		offset = 1;
		// skip other files with same inode number
		while ((i + offset < arraysize) && (array[i]->st_size == array[i+offset]->st_size)
				 && (array[i]->st_ino == array[i+offset]->st_ino)) { 
			if (fverbose) cout << "Is linked to: " << array[i+offset]->name << endl;
			array[i+offset]->processed = true;
			if (fzenity) progress++;
			if (fzenity) if (time(NULL) != timeupdate) {
				cout << progress*100 / progressmax << endl;
				cout << "#[4/4] Recherche de doublons (checked: " << progress << "/" << progressmax << ", saved: " << 512*saved/1024/1024 << " Mo)" << endl;
				timeupdate = time(NULL);
			}
			offset++;
		}
		// compare with other files (differente inode number)
		while ((i + offset < arraysize) && (array[i]->st_size == array[i+offset]->st_size)) { 
			if (fverbose) cout << "Testing similarity to: " << array[i+offset]->name;
			if (compare_files(array[i], array[i+offset])) {
					
				if (!ftest) {
					error = unlink(array[i+offset]->name);
					if (error) {
						cerr << "Unlink failed - error:" << error << endl;
						perror("unlink");
						continue;
					} 
					error = link(array[i]->name, array[i+offset]->name);
					if (error) {
						cerr << "Link failed - error:" << error << endl;
						perror("link");
						exit(-1);
					} 
				} 

				array[i+offset]->processed = true;
				progress++;
				saved += array[i+offset]->st_blocks;
				if (fzenity) if (time(NULL) != timeupdate) {
					cout << progress*100 / progressmax << endl;
					cout << "#[4/4] Recherche de doublons (checked: " << progress << "/" << progressmax << ", saved: " << 512*saved/1024/1024 << " Mo)" << endl;
					timeupdate = time(NULL);
				}
				if (fverbose) cout << " yes !" << endl;
				// Change inode !

				offset2 = 1;
				// also change other files with same inode number
				while ((i + offset + offset2 < arraysize) 
						&& (array[i+offset]->st_size == array[i+offset+offset2]->st_size) 
						&& (array[i+offset]->st_ino == array[i+offset+offset2]->st_ino)) { 
					//cout << "And also: " << array[i+offset+offset2]->name << endl;
					array[i+offset+offset2]->processed = true;
					progress++;
					// Change inode !
					
					if (!ftest) {
						error = unlink(array[i+offset+offset2]->name);
						if (error) {
							cerr << "Unlink failed - error:" << error << endl;
							perror("unlink");
							continue;
						} 
						error = link(array[i]->name, array[i+offset+offset2]->name);
						if (error) {
							cerr << "Link failed - error:" << error << endl;
							perror("link");
							exit(-1);
						} 
					} 

					if (fzenity) if (time(NULL) != timeupdate) {
						cout << progress*100 / progressmax << endl;
						cout << "#[4/4] Recherche de doublons (checked: " << progress << "/" << progressmax << ", saved: " << 512*saved/1024/1024 << " Mo)" << endl;
						timeupdate = time(NULL);
					}
					offset++;
				}

			} else {
				if (fverbose) cout << " no..." << endl;
			}
			offset++;
		}
		array[i]->processed = true;
		i++;
		progress++;
		if (fzenity) if (time(NULL) != timeupdate) {
			cout << 100.0 * progress / progressmax << endl;
			cout << "#[4/4] Recherche de doublons (checked: " << progress << "/" << arraysize << ", saved: " << 512*saved/1024/1024 << " Mo)" << endl;
			timeupdate = time(NULL);
		}
	}
	
	cout << "#Terminé (checked: " << progress << ", saved: " << saved << ")" << endl;
}
/*

*/	// cout << "Size:" << sizeof(&buffer) << "\n";


	



bool dupmerge2 :: compare_files(dupentry* e1, dupentry* e2)
{
	bool ret = false;
	long i, j; // index to go through array

	ifstream f1(e1->name, ifstream::in);
	ifstream f2(e2->name, ifstream::in);
	if (!f1.good()) {
		cerr << "Could not open file " << e1->name << endl;
		return false;
	}
	if (!f2.good()) {
		cerr << "Could not open file " << e2->name << endl;
		return false;
	}

/*
	long progress = 0, speed, elapsed;
	int i;
	long clocks2 = clocks;
*/
	while (f1.good() && f2.good()) {
		f1.read(buffer1, bufferlength);
		f2.read(buffer2, bufferlength);

	/*	
		if ((time(NULL) != timeupdate) && (time(NULL) > 3+clocks2)) {
			elapsed = time(NULL) - clocks2;
			if (elapsed > 0) {
				speed = progress / elapsed;
				cout << progress*100 / e1->st_size << endl;
				cout << "#[4/4] Recherche de doublons - size " << e1->st_size/1024/1024 << " (" << progress << "/" << e1->st_size 
						<< ", " << speed/1024/1024 << "Mo/s)" << endl;
				clocks = time(NULL);
			}
		}*/
		for (i=0; (i<bufferlength) && (j + i < e1->st_size) ; i++)
			if (buffer1[i] != buffer2[i]) {
				f1.close(); f2.close();
				return false;
			}
		j += bufferlength;
	}

	if ((!f1.good()) && (!f2.good()))
		ret = true;
	else {
		cerr << "### La lecture du fichier n'est pas finie !" << endl;
		f1.close(); f2.close();
		exit(-1);		
	}
	f1.close(); f2.close();
	return ret;
}
